浅谈"n个球"和"m个盒子"之间的乱伦关系

无视标题，从我做起

update in 2018.10.1：

补充了"至多为1的四中情况"

这玩意儿的官方名字应该是叫"Twelvefold way"，共用12种情况。

该情况为经典的第二类斯特灵数

设\(f[n][m]\)表示答案。

\(f[n][m] = f[n - 1][m - 1] + m \times f[n - 1][m]\)

边界条件：\(f[0][0] = 1\)

答案 = 第\(n\)个数单独占一个盒子 + 第\(n\)个数和之前的数共占一个盒子，同时考虑不同位置的贡献

注意最后要乘\(m\)，因为第\(n\)个数放置的位置对答案是有影响的

例如{1}{2 4}{3}与{1}{2}{3 4}是不同的方案

题目中的应用

直接枚举用了多少个盒子

设\(g[n][m]\)表示答案

则\(g[n][m] = \sum_{i = 0}^m g[n][i]\)

此类"至多放\(1\)"的问题若\(n>m\)则方案数一定为\(0\)

答案为\([n = m \\ f[n][m - 1] &n < m \end{cases}\)

解释一下：

我们考虑这\(m\)个位置中是否有空盒子

显然：答案 = \(m\)个位置中至少有\(1\)个位置为空的方案 + \(m\)个位置中全不为空的方案

我们可以先在所有盒子里都放了一个，然后对剩下的球讨论

同样可以得到一个结论：

\(n\)个相同的球，放到\(m\)个相同的盒子里，盒子不能为空的方案数 与把整数\(n\)拆成\(m\)段，每段不能为\(0\)的方案数相同

设\(g[n][m]\)表示\(n\)个小球放到\(m\)个相同的盒子里，盒子不能为空的方案数

则\(g[n][m] = f[n - m][m]\)，

题目链接

\(ans = [n